package sorting.algorithms;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;


/**
 * InsertionSort
 * @author mark
 */

public class InsertionSort implements SortingAlgorithm{
	
	/**
	 * sorts a list based on the insertion sort algorithm
	 * @param list of int's
	 * @return sorted list
	 */
	public List<Comparable> sort( List<Comparable> toSort ){
		LinkedList<Comparable> result = new LinkedList<Comparable>();
		for (Comparable c : toSort){
			if (result.isEmpty()){
				result.add(c);				
			} else {
				int count = 0;
				boolean found = false;
				while (count < result.size() && !found){
					if (result.get(count).compareTo(c) > 0){
						result.add(count, c);
						found = true;
					}
					count++;
				}
				if (!found){
					result.add(c);
				}
			}
		}
		return result;
	}

	@Override
	public String getName() {
		return "InsertionSort";
	}
}
